BFS relies on a FIFO queue to process nodes, ensuring a layer-by-layer exploration. Now we visualize both the queue and the graph side-by-side.

  • The heart of BFS is a FIFO (First-In, First-Out) queue.
  • When we visit a node (dequeue from the front), we discover all of its previously unseen neighbors and enqueue them at the back.
  • The queue dictates the next node to visit, ensuring level-by-level exploration (increasing distance from the start).
  • On the right, the graph highlights the node being visited and the discovery edges; the queue shows the order of processing.
Python Queue (deque)
from collections import deque

# A deque is an efficient double-ended queue
q = deque()

q.append('A')   # Enqueue 'A'
q.append('B')   # Enqueue 'B'
# Queue is now: ['A', 'B']

x = q.popleft() # Dequeue from the left (front)

print(x)        # Output: 'A'